import random
import math

def euclidean_distance(x, y):
    """计算两点之间的欧式距离"""
    return math.sqrt(sum((a - b) ** 2 for a, b in zip(x, y)))

def assign_cluster(x, centers):
    """将样本 x 分配给最近的中心，返回其索引"""
    distances = [euclidean_distance(x, c) for c in centers]
    return distances.index(min(distances))

def mean_point(points):
    """计算一个簇中所有点的均值作为新的中心"""
    n = len(points)
    if n == 0:
        return None
    dim = len(points[0])
    return [sum(p[i] for p in points) / n for i in range(dim)]

def Kmeans(data, k, epsilon=1e-4, iteration=100):
    """手动实现 K-means 聚类"""
    # 1️⃣ 随机初始化 k 个中心
    centers = random.sample(data, k)
    for it in range(iteration):
        # 2️⃣ 为每个样本分配簇
        clusters = [[] for _ in range(k)]
        for x in data:
            idx = assign_cluster(x, centers)
            clusters[idx].append(x)

        # 3️⃣ 计算新的中心
        new_centers = []
        for cluster in clusters:
            center = mean_point(cluster)
            # 防止空簇
            if center is None:
                center = random.choice(data)
            new_centers.append(center)

        # 4️⃣ 判断是否收敛
        max_shift = max(euclidean_distance(c1, c2) for c1, c2 in zip(centers, new_centers))
        print(f"迭代 {it+1}: 最大中心变化量 = {max_shift:.6f}")
        if max_shift < epsilon:
            print("算法收敛！")
            break
        centers = new_centers

    # 5️⃣ 最终簇分配
    labels = [assign_cluster(x, centers) for x in data]
    return centers, labels